package July;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author:gao
 * @date:2020/7/2
 * @time:8:47
 * @version:0.0.1
 * @description:none
 */

public class KthSmallest {
    public static void main(String[] args) {
        int[][] a ={
                { 1,  5,  9},
                {10, 11, 13},
                {12, 13, 15}};
        int k = 8;
        Solution solution = new Solution();
        solution.kthSmallest(a,k);
    }
}

//我的five方法，用一个数组标记每一行的未被选择的元素的开始位置
//class Solution {
//    public int kthSmallest(int[][] matrix, int k) {
//        int row = matrix.length;
//        int col = matrix[0].length;
//        int[] rowStart = new int[row];
//        int min = Integer.MAX_VALUE;
//        for(int i=0;i<k;i++){
//            min = Integer.MAX_VALUE;
//            int minIndex =-1;
//            for(int j=0;j<row;j++){
//                if(rowStart[j]==col) continue;
//                if(matrix[j][rowStart[j]]<min){
//                    min=matrix[j][rowStart[j]];
//                    minIndex=j;
//                }
//            }
//            rowStart[minIndex]++;
//            //System.out.println(min);
//        }
//        return min;
//    }
//}


//题解的优先队列（堆）方法优化
//top k 问题
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        //用优先队列来实现堆，定义一个比较接口
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }//感觉是返回值大于0就交换，这样最后就是
                                                                        //按照从小到大排序，不是很确定
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            //先把每行第一个放进去
            pq.offer(new int[]{matrix[i][0], i, 0});//1.数字 2.行 3.列
        }
        //一次加进去占用空间多
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();//找到最小的
            if (now[2] != n - 1) {//判断是否是当前行的最后一个，不是就把下一个加进去
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
}


//还有最优化的解法，但是有点想不到